This disclosure relates generally to data decoding, and more particularly to iterative decoders for data encoded with a low-density parity check (LDPC) encoder.
LDPC codes may be represented by many different types of parity check matrices. The structure of an LDPC code's parity check matrix may be, for example, random, cyclic, or quasi-cyclic. LDPC codes defined by quasi-cyclic parity check matrices are particularly common and computationally efficient. These codes are known as quasi-cyclic low density parity check (QC-LDPC) codes.
As used herein, the term message refers to a numerical value, usually representing a log likelihood ratio (LLR). A LDPC decoder may decode LDPC codes using an iterative message passing algorithm, such as a min-sum decoding algorithm. Such algorithms may decode a received codeword using an iterative process in which each iteration includes two update steps involving check nodes and variable nodes.
A LDPC decoder may also use a layered approach to decoding (layered decoding) to decode LDPC codes. For a QC-LDPC code with a quasi-cyclic parity check matrix consisting of circular submatrices (circulants) of size Sc, the number of check node processors necessary to implement layered decoding in the LDPC decoder may be Sc. This quantity is the parallelization level. Within a LDPC decoder, the layered decoding approach for a QC-LDPC codeword may require a circular shifter to be used. The circular shifter may be responsible for shifting Sc LLR messages, each from a different check node processor, in one layer of processing. The amount of shift may be determined by the maximum shift necessary for a message. At greatest, the maximum shift may be equal to, Sc, the size of the circulants in the quasi-cyclic parity check matrix associated with the QC-LDPC code. In this case, a Sc input, Sc output circular shifter may be used to appropriately shift the LLR messages. This Sc×Sc circular shifter may be implemented using a barrel shifter that hierarchically shifts the input sequence of each of the LLR messages in ceil(log2(Sc)) steps. The complexity of this circular shifter may therefore be proportional to ceil(log2(Sc)).
The LLR messages may also have to be initially shifted prior to the start of the decoding process. These LLR messages may be the initial messages sent to a LDPC decoder by, for example, a channel detector. In particular, these LLR messages may be the initial messages sent to a group of (grouped) variable nodes associated with a circulant of a quasi-cyclic parity check matrix in a mother matrix representation. Prior to the start of the decoding process, these messages may have to be appropriately shifted so that the computation and subsequent shifting of messages sent from the variable nodes to the check nodes is correct. The amount that the LLR messages must be shifted may be determined by the difference in shifts between the first non-zero circulant in the column associated with the grouped variable nodes to which the LLR messages are sent and the previous non-zero circulant in the same column of the quasi-cyclic parity check matrix in the mother matrix representation. LLR messages may be sent from, for example, a channel detector to a layered LDPC decoder in segments smaller than circulant size, Sc. LLR messages may be sent in this manner because of the bandwidth constraints in the channel between a channel detector and a layered LDPC decoder. Subsequent shifting of LLR messages may be done by the circular shifter used in layered decoding.
The performance capability of a coding scheme, such as a LDPC coding scheme, is often described by the code's performance curve. The performance curve is a plot of signal-to-noise ratios (SNR) vs. Bit Error Rate (BER), or equivalently Sector Error Rate (SER). A tradeoff may exist between the performance of a QC-LDPC code, predefined or designed, and the complexity of the circular shifter used in layered decoding of the QC-LDPC code.
In terms of complexity, the circular shifter used in decoding a QC-LDPC code, predefined or designed, may be one of the dominant modules which may, depending on the size of the code, comprise 20-30% of the total complexity of the LDPC decoder. A highly complex circular shifter may nominally increase the performance of a predefined or designed QC-LDPC code, but may disadvantageously lead to computational inefficiency, increased routing congestion and more difficult timing closure. Moreover, such computational inefficiency, increased routing congestion, and more difficult timing closure may lead to degraded application performance.
Therefore, there exists a need for LDPC decoders using circular shifters of reduced complexity which decode predefined or designed QC-LDPC codes. Furthermore, there exists a need to have methods to design codes which may have particular LDPC code performance capabilities and which may operate with such decoders using reduced-complexity circular shifters. Moreover, there exists a need to appropriately shift LLRs prior to the start of the layered decoding approach used by such decoders using reduced-complexity circular shifters. For example, decoding predefined or designed QC-LDPC codes using LDPC decoders with reduced-complexity circular shifters that limit the amount of shift to a small value may acceptably decrease the LDPC code performance capability and may lead to increased computational efficiency, decreased routing congestion, and easier timing closure. Therefore, there exists a need, for example, for LDPC decoders which use reduced-complexity circular shifters that limit the amount of shift to a small value. There also exists a need, for example, for designed QC-LDPC codes which may have particular LDPC code performance capabilities and which may be decoded using LDPC decoders using reduced complexity circular shifters. Increased computational efficiency, decreased routing congestion, and easier timing closure of these types of decoders may lead to improved application performance.